package com.jar.exercise.集合和数据结构.红黑树;

public class RedBlackTree {
	int data;
	private final int R = 0;
	private final int B = 1;

	private Node root;

	class Node {
		Node parent;
		Node left;
		Node right;
		int data;
		int color = R;

		public Node(int data) {
			this.data = data;
		}
	}

	/**
	 * 插入
	 */
	public void insert(Node node, int data) {
		if (data > node.data) {
			if (node.right == null) {
				node.right = new Node(data);
			} else {
				insert(node.right, data);
			}
		} else {
			if (node.left == null) {
				node.left = new Node(data);
			} else {
				insert(node.left, data);
			}
		}
	}

	/**
	 * 左旋
	 */
	public void leftHand(Node node) {
		// 如果node就是根节点
		if (node.parent != null) {
			// 1.此节点变为根节点
			Node parentNode = node.parent;
			node.parent = null;
			// 根节点的父节点指向此节点
			parentNode.parent = node;
			// 2.父节点的右节点指向此节点的左节点；此节点的左节点指向父节点
			parentNode.right = node.left;
			node.left = parentNode;
		} else {
			// 1.此节点变为根节点
			Node parentNode = root;
			// 根节点的父节点指向此节点
			parentNode.parent = node;
			// 2.父节点的右节点指向此节点的左节点；此节点的左节点指向父节点
			parentNode.right = node.left;
			node.left = parentNode;
		}
	}

	/**
	 * 右旋
	 */
	public void rightHand(Node node) {
		if (node.parent != null) {
			Node parent = node.parent;
			//父节点的指向此节点
			parent.parent = node;
			//父节点的左节点变为此节点的右节点；此节点的右节点变为父节点的左节点
			parent.left = node.right;
			node.right = parent.left;
			// 1.此节点变为根节点
			node.parent = null;
		} else {
			Node parent = root;
			//父节点的指向此节点
			parent.parent = node;
			//父节点的左节点变为此节点的右节点；此节点的右节点变为父节点的左节点
			parent.left = node.right;
			node.right = parent.left;
			// 1.此节点变为根节点
		}
	}

	/**
	 * 改变为红色
	 */
	private void changRed(Node node) {
		node.color = R;
	}

	/**
	 * 改变为黑色
	 */
	private void changBlack(Node node) {
		node.color = B;
	}

	public void changeColor(Node node) {
		if (node.parent != null) {
			Node parent = node.parent;
			// 如果父节点为红色的,没有祖父节点
			if (parent.color == R && parent.parent == null) {
				// 修改父亲节点为黑色
				changBlack(parent);
			}
			if (parent.color == R && parent.parent != null) {
			}
		}
	}

	/**
	 * 根据值查询节点
	 */
	public Node query(int data) {
		Node root = this.root;
		while (root != null) {
			if (root.data == data) {
				return root;
			} else if (data > root.data) {
				root = root.right;
			} else {
				root = root.left;
			}
		}
		return null;
	}
}
